翻訳と辞書 Words near each other ・ TBWA Worldwide ・ TBWA\Chiat\Day ・ TBX1 ・ Tbx18 transduction ・ TBX19 ・ TBX2 ・ TBX20 ・ TBX21 ・ TBX22 ・ TBX3 ・ TBX4 ・ TBX5 (gene) ・ TBX6 ・ TBZ ・ TC ・ TC (complexity) ・ Tc (Linux) ・ TC (musician) ・ TC 2000 (film) ・ TC 2000 Championship ・ TC 46/SC 9 ・ TC Beirne Department Store ・ TC Beirne School of Law ・ TC Business School ・ TC Digital Games ・ TC Electronic ・ TC Elima ・ TC EMPIRE Trnava ・ TC Group ・ TC Huo Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク TC (complexity) ： ウィキペディア英語版 TC (complexity) In theoretical computer science, and specifically computational complexity theory and circuit complexity, TC is a complexity class, and TCi is a hierarchy of complexity classes. Each class TCi consists of the languages recognized by Boolean circuits with depth $O(\backslash log^i\; n)$ and a polynomial number of unlimited-fanin AND, OR gates and Majority gates. The class TC is defined as :$\backslash mbox\; =\; \backslash bigcup\_\; \backslash mbox^i.$ ==Relation to NC and AC== The relationship between the TC, NC and the AC hierarchy can be summarized as :$\backslash mbox^i\; \backslash subseteq\; \backslash mbox^i\; \backslash subseteq\; \backslash mbox^i\; \backslash subseteq\; \backslash mbox^.$ In particular, we know that :$\backslash mbox^0\; \backslash subsetneq\; \backslash mbox^0\; \backslash subsetneq\; \backslash mbox^0\; \backslash subseteq\; \backslash mbox^.$ The first strict containment follows from the fact that NC0 cannot compute any function that depends on all the input bits. Thus choosing a problem that is trivially in AC0 and depends on all bits separates the two classes. (For example, consider the OR function.) The strict containment AC0 ⊊ TC0 follows because parity and majority (which are both in TC0) were shown to be not in AC0.〔M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. ''Math. Systems Theory'', 17:13–27, 1984.〕 As an immediate consequence of the above containments, we have that NC = AC = TC. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「TC (complexity)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.